package com.zjw.algorithm.ready1;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

public class _双栈队列 {


}


class MyQueue {

    private final Stack<Integer> stackIn = new Stack<>();
    private final Stack<Integer> stackOut = new Stack<>();

    public MyQueue() {

    }

    public void push(int x) {
        if (stackIn.isEmpty()) {
            while (!stackOut.isEmpty()) {
                stackIn.push(stackOut.pop());
            }
        }
        stackIn.push(x);
    }

    public int pop() {
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.pop();
    }

    public int peek() {
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.peek();
    }

    public boolean empty() {
        return stackOut.isEmpty() && stackIn.isEmpty();
    }
}


class MyStack {

    private final Queue<Integer> queue1 = new ArrayDeque<>();
    private final Queue<Integer> queue2 = new ArrayDeque<>();

    private boolean use1 = true;

    public MyStack() {

    }

    public void push(int x) {
        if (use1) {
            queue1.offer(x);
        } else {
            queue2.offer(x);
        }
    }

    public int pop() {
        Queue<Integer> outQueue = use1 ? queue1 : queue2;
        Queue<Integer> inQueue = use1 ? queue2 : queue1;

        while (outQueue.size() > 1) {
            inQueue.offer(outQueue.poll());
        }

        //每pop一次，就逆反一次
        use1 = !use1;

        return outQueue.poll();
    }

    public int top() {
        Queue<Integer> outQueue = use1 ? queue1 : queue2;
        Queue<Integer> intQueue = use1 ? queue2 : queue1;

        while (outQueue.size() > 1) {
            intQueue.offer(outQueue.poll());
        }

        //每pop一次，就逆反一次
        use1 = !use1;

        Integer result = outQueue.poll();
        intQueue.offer(result);
        return result;
    }

    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}